#ifndef STX_ALGORITHM_MAKE_HEAP_HPP
#define STX_ALGORITHM_MAKE_HEAP_HPP

#include <stx/algorithm/common.hpp>
#include <stx/algorithm/push_heap.hpp>

namespace stx {

template <class Compare, class RandomAccessIterator>
inline void
make_heap_impl(RandomAccessIterator first, RandomAccessIterator last, Compare comp)
{
    typedef typename std::iterator_traits<RandomAccessIterator>::difference_type difference_type;
    difference_type n = last - first;
    if (n > 1) {
        last = first;
        ++last;
        for (difference_type i = 1; i < n;) {
            push_heap_back<Compare>(first, ++last, comp, ++i);
        }
    }
}

template <class RandomAccessIterator, class Compare>
inline void
make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp)
{
    typedef typename add_lvalue_reference<Compare>::type comp_ref;
    make_heap_impl<comp_ref>(first, last, comp);
}

template <class RandomAccessIterator>
inline void
make_heap(RandomAccessIterator first, RandomAccessIterator last)
{
    stx::make_heap(
        first,
        last,
        stx::less<typename std::iterator_traits<RandomAccessIterator>::value_type>());
}

} // namespace stx

#endif // STX_ALGORITHM_MAKE_HEAP_HPP
